//
// Created by ki on 2021/3/3.
//

/*
 * 快排思路：
 * 1）确定分界点（左端点，右端点，中间断点）
 * 2）调整区间（小于选定数放左边，大于选定数放右边）
 * 3）递归处理左右两个区间
 *
 * 最坏的时间复杂度是O(n^2)，平均时间复杂度O(nlog(n))
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;

class Random
{
public:
	Random() { mt.seed(time(nullptr)); }
	int operator()(int low, int high)
	{
		uniform_int_distribution<int> uid(low, high);
		return uid(mt);
	}
private:
	mt19937 mt;
};

Random random;

template <typename T>
void quick_sort(vector<T>& q, int l, int r)
{
	if (l >= r) return;
	T mid = q[random(l, r)]; //q[(l + r) >> 1]
	int i = l - 1, j = r + 1;
	while (i < j)
	{
		do ++i; while (q[i] < mid);
		do --j; while (q[j] > mid);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

int main()
{
	vector<int> nums;
	for (int i = 0; i < 2000; ++i)
		nums.push_back(random(0, 199));
	quick_sort(nums, 0, nums.size() - 1);
	for (auto x : nums)
	{
		cout << x << ' ';
	}
}
